package leetcode.code1937;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	// 去绝对值
	public long maxPoints(int[][] points) {
		int m = points.length, n = points[0].length;
		long[] dp = new long[n];// dp[i] 以 i 列为结束的最大值。
		// 只有一行时, 每一列就是dp[i]的结果
		long ans = 0;
		for (int i = 0; i < n; i++) {
			dp[i] = points[0][i];
//			ans = Math.max(ans, dp[i]);
		}
		for (int i = 1; i < m; i++) {
			long[] row = new long[n];
			// 上一行，大值出现在当前行选择的列的左侧 去绝对值 dp[i] + j
			long max = Integer.MIN_VALUE;
			for (int j = 0; j < n; j++) {
				max = Math.max(max, dp[j] + j);
				row[j] = max + points[i][j] - j;
//				ans = Math.max(ans, row[j]);
			}
			max = Integer.MIN_VALUE;
			// 上一行，大值出现在当前行选择的列的右侧侧 去绝对值 dp[i] - j
			for (int j = n - 1; j >= 0; j--) {
				max = Math.max(max, dp[j] - j);
				row[j] = Math.max(row[j], max + points[i][j] + j);
//				ans = Math.max(ans, row[j]);
			}
			dp = row;
		}
		// dp中找个最大的
//		long ans = 0;
		for (int i = 0; i < n; i++) {
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(9, this.maxPoints(HelpDebug.str2array1("[[1,2,3],[1,5,1],[3,1,1]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
